#!/usr/bin/python
# http://www.programminginterviews.info/2011/05/string-pattern-matching.html
# 
# String Pattern matching
# 

def match(target, source):
	# Take in 2 strings, and search for the target string in the source string
	# Return the position of the match, or -1 if no match. 
	
	if (len(target) > len(source)):
		return -1
		
	for i in range(len(source) - len(target)):
		targetPos = 0
		sourcePos = i
				
		while( (source[sourcePos] == target[targetPos]) and (targetPos < (len(target) - 1))):
			targetPos += 1
			sourcePos += 1
			
		
		if (targetPos == len(target)-1):
			return i
		
	return -1
		
def main():
	text = "Search for a string in another string\n"
	
	source = raw_input("Source string >")
	target = raw_input("Target string >")
	
	isMatch = match(target,source)

	if ( isMatch == -1 ):
		print "Sorry, no match found"
	else:
		print "Match found at source position " + str(isMatch)
		
		
if __name__ == "__main__":
	main()